The present invention relates to a turbo decoding apparatus and interleave-deinterleave apparatus suitable for use in, for example, a communication system such as a mobile communication system.
In a conventional wireless communication field including a mobile communication or the like, a device of interleaver and corresponding deinterleaver are introduced to sort the data series in order to make a burst error, which tends to occur frequently at a particular portion of the data series, corrected more easily. That is, a transmitting signal is transmitted after interleaved by an interleaver on the transmitting side, and received on the receiving side, and then the signal is deinterleaved by a deinterleaver.
A conventional interleaver and deinterleaver will hereinafter be described.
FIG. 6(A) is a block diagram showing an arrangement of a conventional interleaver. As shown in FIG. 6(A), an interleaver 100 comprises an interleave RAM 101, a writing counter 102, a reading counter 103 and a reading address converting circuit 104. The interleaver 100 shown in FIG. 6 (A) is arranged based on an assumption that the interleaver interleaves an input data series composed of 24xc3x9716=384 pieces of data (D000, D001, D002, . . . , D383) (i.e., the interleaver size=24xc3x9716).
In this case, the interleave RAM 101 (hereinafter denoted simply as xe2x80x9cRAM 101xe2x80x9d) is a unit for storing therein the input data series (D000, D001, D002, . . . , D383) for interleave operation. The writing counter 102 is a unit for counting the numbers from 0 to 383 sequentially and outputs the counted value as a writing address (A000, A001, A002, . . . , A383) for the RAM 101. Thus, the input data series are sequentially written in the RAM 101 at addresses from A000 to A383 in accordance with the writing address (A000 to A383).
The reading counter 103 is a unit for counting a series of numbers from 0 to 383 for generating the reading address for the RAM 101. The reading address converting circuit 104 is a unit for effecting an arithmetic operation expressed by x*16(mod383) on the counted number x (=0 to 383) supplied from the reading counter 103, thereby converting the series of counted numbers x generated from the reading counter 103 into one having a regular interval of 16. Thus, the series of reading addresses supplied to the RAM 101 becomes a series of addresses having a regular interval of 16 such that A000, A016, A032, . . . , A368, A001, A017, A033, . . . , An*16(mod383), . . . , A351, A367, A383.
If the interleaver 100 is arranged as described above, as shown in FIG. 6(B), when data is written into the memory, the counted value of the writing counter 102 directly serves as the writing address and the input data series (D000, D001, B002, . . . , D383) are written at the corresponding address regions in the RAM 101 sequentially. On the other hand, when data are read from the memory, data are read from address regions designated by the reading address which are generated at the regular interval of 16 from the reading address converting circuit 104.
In this way, the input data series (D000, D001, B002, . . . , D383) are interleaved, and as a result outputted like D016, D032, . . . , D368, D001, D017, D033, . . . , Dn*16(mod383), . . . , D351, D367, D383.
In other words, the interleave operation carried out in the present interleaver 100 can be illustrated as shown in FIG. 7, for example. That is, when data pieces of 24xc3x9716=384 are written into the RAM 101, the written data are arrayed in the direction indicated by an arrow A in this order while when the same data pieces are read from the memory, data pieces arrayed in the direction indicated by an arrow B are read in this order, whereby the interleave operation is accomplished (this manner of interleave operation is known as block interleave).
Meanwhile, FIG. 8(A) is a block diagram showing an arrangement of a conventional deinterleaver. As shown in FIG. 8(A), the deinterleaver 200 comprises a deinterleave RAM 201, a writing counter 202, a reading counter 203 and a reading address converting circuit 204. The deinterleaver 200 shown in FIG. 8(A) is arranged based on an assumption that the deinterleaver deals with an input data series composed of 16xc3x9724=384 pieces of data (D000, D001, B002, . . . , D383).
In this case, the deinterleave RAM 201 (hereinafter denoted simply as xe2x80x9cRAM 201xe2x80x9d) is a unit for storing therein the input data series (D000, D001, B002, . . . , D383) for interleave operation. The writing counter 202 is a unit for counting the numbers from 0 to 383 sequentially and outputs the counted value as a writing address (A000, A001, A002, . . . , A383) for the RAM 201. Thus, the input data series are sequentially written in the RAM 201 at addresses from A000 to A383 in accordance with the writing address (A000 to A383).
The reading counter 203 is a unit for counting a series of numbers from 0 to 383 for generating the reading address for the RAM 201. The reading address converting circuit 204 is a unit for effecting an arithmetic operation expressed by x*24(mod383) on the counted number x (=0 to 383) supplied from the reading counter 203, thereby converting the series of counted numbers x generated from the reading counter 203 comes to have a regular interval of 24. Thus, the series of reading addresses supplied to the RAM 201 becomes a series of addresses having a regular interval of 24 such that A000, A024, A048, . . . , A360, A001, A002, . . . , An*24(mod383), . . . , A335, A359, A383.
If the interleaver 200 is arranged as described above, as shown in FIG. 8(B), when data is written into the memory, the counted value of the writing counter 202 directly serves as the writing address and the input data series (D000, D001, B002, . . . , D383) are written in the RAM 201 at the corresponding address regions sequentially. On the other hand, when data are read from the memory, data are read from address regions designated by the reading address which are generated at the regular interval of 24 from the reading address converting circuit 204.
In this way, the input data series (D000, D001, B002, . . . , D383) are interleaved and as a result, outputted like D000, D024, D048, . . . , D360, D001, D025, . . . , Dn*24(mod383), . . . , D335, D359, D383. In other words, the operation of the present interleaver 200 is equivalent to an interleave operation at a size of 16xc3x9724. That is, as for example shown in FIG. 9, when data pieces of 16xc3x9724=384 are written into the RAM 201, the written data are arrayed in the direction indicated by an arrow A in this order while when the same data pieces are read from the memory, data pieces arrayed in the direction indicated by an arrow B are read in this order.
Accordingly, if the input data series are interleaved by 24xc3x9716 in the above-described interleaver 100, and the resulting output data series (D000, D016, D032, . . . , D368, D001, D017, D033, . . . , Dn*16(mod383), . . . , D351, D367, D383) are supplied to the present deinterleaver 200, then writing and reading data series are carried out as shown in FIG. 8(C). That is, when writing is carried out, the output data series are written in the RAM 202 in the aforesaid order sequentially and when reading is carried out, data series are read at a regular interval of 24 addresses. As a result, the output data series are restored as one before the interleave operation (i.e., deinterleave operation is effected).
Meanwhile, recently, a new error correcting system known as xe2x80x9cturbo encoding and turbo decodingxe2x80x9d comes to be utilized. According to a communication system having the system of turbo encoding and turbo decoding applied thereto, transmitting information is encoded by an interleaver using a plurality of error correcting codes (recursive systematic convolutional code is often employed) on the transmitting side (in a turbo encoder). Then, on the receiving side (in a turbo decoder), the received information is subjected to an interleave operation, soft-output decoding, and deinterleave operation repeatedly by using an interleaver, a deinterleaver and a plurality of error correcting code (soft-output) decoders. Thus, errors attached to the transmitting information in the transmitting path are reduced as much as possible to restore the original transmitting information.
FIG. 10 is a block diagram showing an example of arrangement of a main portion of a communication system to which the aforesaid xe2x80x9cturbo encoder and turbo decoderxe2x80x9d is applied. As shown in FIG. 10, this communication system is arranged to include a turbo encoder 300 on the transmitting side while a turbo decoder (turbo decoding unit) 400 on the receiving side with a desired communication path (radio communication network and soon) 500 interposed therebetween. The turbo encoder 300 is composed of a pair of recursive systematic convolutional encoders (hereinafter simply referred to as xe2x80x9cconvolutional encoderxe2x80x9d) 301 and 302, each being arranged to include exclusive-OR logical sum elements (EX-OR) 311 to 313 and delay elements (flip-flop: FF) 314 and 315. The turbo encoder also includes an interleaver (xcfx80) 303 for effecting interleave operation on the transmitting information u. The turbo decoder 400 is arranged to include soft-output decoders (DEC) 401 and 402 and interleaver (xcfx80) 403 and deinterleaver (xcfx80xe2x88x921) 404.
The convolutional encoder 301 of the turbo encoder 300 is a unit for sending encoded information obtained by encoding the transmitting information u using convolution operation, to the receiving side as an error correcting code y1. The interleaver 303 is a unit for effecting interleave operation on the transmitting information u using the same operating principle as that of the aforesaid interleaver 100. The convolutional encoder 302 is a unit for sending the encoded information obtained by effecting convolutional encoding on the transmitting information uxe2x80x2 which has been interleaved in the interleaver 303, to the receiving side as an error correcting code y2.
That is, the turbo encoder 300 is arranged for sending the transmitting information (information to be decoded) u itself, the error correcting code y1 about the transmitting information u before the interleave operation and the error correcting code y2 about the transmitting information u after the interleave operation, to the receiving side as a turbo code.
On the other hand, the turbo decoder 400 repetitively carries out the following operations. That is, of the received turbo codes [in this case, it is assumed that the transmitting information u, the error correcting code y1 and y2 suffer from a noise (error) in the transmitting path 500 and they become received information U, error correcting codes Y1 and Y2, respectively], the DEC 401 receives the received information U and effects soft-output decoding thereon by using the error correcting code Y1 so as to obtain received information Uxe2x80x2. Thereafter, the interleaver 403 effects interleave operation of the received information Uxe2x80x2 and the DEC 402 effects soft-output decoding on the interleaved signal by using the error correcting code Y2. Then, the decoded result (received information Uxe2x80x3) is deinterleaved in the deinterleaver 404 and obtained signal is fed back to the DEC 401. The DEC 401 again effects soft-output decoding by using error correcting code Y1. The operations described above is repeated. When the soft-output decoding is effected, MAP (Maximum A Posteriori probability) decoding, SOVA (Soft-Output Viterbi Algorithm) decoding or the like is utilized.
The interleaver 403 also effects interleave operation on the decoded result supplied from the DEC 401 based on the similar operation principle to that the above interleaver 100. With this interleave operation, the data series as a decoding result from the DEC 401 are supplied to the DEC 402 with the data series matched with the data series of the error correcting code Y2 utilized for soft-output decoding in the DEC 402.
Further, the DEC 402 is a unit for effecting soft-output decoding (e.g., MAP decoding, SOVA decoding or the like) on the decoded result having undergone the interleave operation by using the error correcting code Y2. The deinterleaver 404 is a unit for effecting deinterleave operation on the decoded result supplied from the DEC 402 based on the similar operating principle to that of the aforesaid deinterleaver 200, thereby restoring the original data series. With this deinterleave operation, the data series as a result of decoding supplied from the DEC 402 are supplied to the DEC 401 with the data series matched with the data series of the error correcting code Y1. Thus, the data series are again subjected to soft-output decoding by using the error correcting code Y1 in the DEC 401.
As the following operation is repeated in the turbo decoder 400, errors attached to the transmitting information u tend to be removed from the information, and hence the original transmitting information u can be restored with higher degree of accuracy.
1. U undergoes soft-output decoding by using Y1. xe2x86x92Uxe2x80x2
2. Uxe2x80x2 undergoes soft-output decoding by using Y2. xe2x86x92Uxe2x80x3
(output undergoing one-time turbo cycle repeat)
3. Uxe2x80x3 undergoes soft-output decoding by using Y1. xe2x86x92Uxe2x80x23 
4. Uxe2x80x23 undergoes soft-output decoding by using Y2. xe2x86x92Uxe2x80x24 
(output undergoing two-time turbo cycle repeat)
5. Uxe2x80x24 undergoes soft-output decoding by using Y1. xe2x86x92Uxe2x80x25 
4. Uxe2x80x25 undergoes soft-output decoding by using Y2. xe2x86x92Uxe2x80x26 
(output undergoing three-time turbo cycle repeat)
(the same operation may be similarly repeated)
The repeating time is set equal to or less than a saturating number (e.g., about 16 times).
In this way, the turbo decoder 400 repeats the operations of soft-output decoding, interleave and deinterleave by using the DECs 401 and 402, the interleaver 403 and the deinterleaver 404, whereby data encoded by the turbo coding system can be decoded. The turbo encoding and turbo decoding are described in detail in a reference such as U.S. Pat. No. 5,446,747, for example.
According to the above-described turbo decoder 400, the operations of interleave and deinterleave are effected independently by the interleaver 403 and the deinterleaver 404. Therefore, the turbo decoder necessarily comes to have a very large-sized circuit.
In particular, in an actual communication situation, a single unit (in the above example of the data series, each of D000 to D383) of data series (data series as a target of interleave or deinterleave operation) as a decoding result comes to have several tens bits amount. If the single unit of the data series comes to have such a large size, the size of the interleaver (or deinterleaver) (i.e., memory size) will come to have several thousands bits amount, with the result that the above-identified problem will become more conspicuous.
Further, there is a chance that any arrangement other than the turbo decoder 400 will encounter the above-identified problem. That is, if a transmitter-receiver is arranged to communicate by using an interleaver and a corresponding deinterleaver, it is indispensable to prepare both of the interleaver 100 and the deinterleaver 200 independently if the transmitter-receiver is arranged based on the currently available technology. Therefore, the size of the apparatus will similarly become very large.
The present invention is made in view of the above aspect. Therefore, an object of the present invention is to provide a turbo decoding apparatus and an interleave-deinterleave apparatus which makes it possible to remarkably reduce the size of the apparatus.
In order to attain the above object, there is provided a turbo decoding apparatus of the present invention contains at least information to be decoded, an error correcting code for the information which is to be decoded and has not been interleaved on a transmitting side, and an error correcting code for the information which is to be decoded and has been interleaved on the transmitting side while an interleave operation and a deinterleave operation is repetitively carried out together with an error correcting code, characterized by including an error correction decoding unit capable of effecting error correction and decoding on the information to be decoded based on either one of the error correcting codes and a result of error correction and decoding which has been done in a preceding stage, a memory unit for effecting interleave operation and deinterleave operation on the result of error correction and decoding operation provided from the error correction decoding unit, and for outputting the data deriving from the error correction and decoding operation to the error correction decoding unit as a result of error correction and decoding operation which has been done in a preceding stage, and a memory control unit for controlling the order of writing/reading the result of error correction and decoding operation into/from the memory unit so that interleave operation and deinterleave operation can be effected on the result of error correction and decoding operation depending on the error correcting code utilized in the error correction decoding unit.
According to the turbo decoding apparatus of the present invention, by controlling the writing order and the reading order of the data in accordance with the error correcting code utilized in the error correction decoding unit, the data as the result of error correction decoding can be interleaved and deinterleaved. Therefore, it is unnecessary to provide an interleaver and a deinterleaver independently, thereby minimizing the size and cost of the turbo decoding apparatus.
The memory control unit may be arranged to include the following components:
(1) a first address generating unit for generating a series of addresses in a predetermined order for the memory unit;
(2) a second address generating unit for generating a series of addresses for the memory unit in an order which is different from that of the first address generating unit;
(3) a pair of address selecting units for selectively connecting one of outputs of the address generating units as a writing address of the memory unit while the other of the outputs of the address generating units as a reading address for the memory unit;
(4) an interleave mode determining unit for determining whether the error correcting code utilized in the error correction decoding unit is one arranged for the information which is to be decoded before interleave operation on the transmitting side or one arranged for the information which is to be decoded after interleave operation on the transmitting side; and
(5) an address selection control unit for controlling the pair of address selecting units in such a manner that if the interleave determining unit determines that the error correcting code is one arranged for the information to be decoded before interleave operation, then one of the outputs of the address generating units is selected as the writing address while the other of outputs of the address generating units is selected as the reading address, and if the interleave determining unit determines that the error correcting code is one arranged for the information to be decoded after interleave operation, then the other of the outputs of the address generating units is selected as the writing address while that one of the outputs of the address generating units is selected as the reading address.
According to the above arrangement of the turbo decoding apparatus of the present invention, if the outputs from the first address generating unit and the second address generating unit are selectively controlled, the resulting data of the error correction decoding data can be satisfactorily controlled in the writing order and the reading order of the data on the memory unit depending on which the interleave or deinterleave is requested. Therefore, the present turbo decoding apparatus having extremely simple construction can be realized.
The second address generating unit may include a random pattern holding unit having random pattern information held therein for changing the sequence of addresses generated from the first address generating unit at random and outputting a series of addresses therefrom. If the second address generating unit is arranged as above, it becomes unnecessary to prepare two sets of random pattern information for interleave operation and deinterleave operation (i.e., the first address generating unit can be made to serve as not only a unit for interleave operation but also a unit for deinterleave operation). Therefore, cost for carrying out arithmetic operation requested upon determining the random pattern in advance can be remarkably reduced, and moreover the turbo decoding apparatus can be made smaller and constructed at an extremely low cost.
Further, according to the present invention, there is provided an interleaving-deinterleaving apparatus which includes a memory unit for storing therein data so that the data can be subjected to interleave and deinterleave operation, a first address generating unit for generating a series of addresses in a predetermined order for the memory unit, a second address generating unit for generating a series of addresses to the memory unit in an order which is different from that of the first address generating unit, a pair of address selecting units for selectively outputting one of outputs from the address generating units for a writing address of the memory unit while the other one of the outputs from the address generating units for a reading address for the memory unit, and an address selection control unit for controlling the pair of address selecting units in such a manner that the pair of address selecting units selects the outputs of the address generating units as the writing address and the reading address depending on the cases in which the data is requested to be interleaved or to be deinterleaved.
According to the above interleave-deinterleave apparatus of the present invention, one of outputs from the address generating units (two kinds of address data series differing from each other in its generating order) can be selected as the writing address or the reading address depending on whether the data is to be interleaved or to be interleaved. Therefore, the single memory unit can function as not only an interleaver but also as a deinterleaver. As a result, it becomes unnecessary to independently provide an interleaver and a deinterleaver for carrying out interleave operation and deinterleave operation, with the result that the apparatus can be made small and hence the apparatus can be constructed at an extremely low cost.
In this case, the address selection control unit may be arranged to control the pair of address selecting units in such a manner that if the data is to be interleaved, the output of the first address generating unit is selected as the writing address while the output of the second address generating unit is selected as the reading address, respectively, and if the data is to be deinterleaved, the output of the second address generating unit is selected as the writing address while the output of the first address generating unit is selected as the reading address, respectively.
Conversely, the address selection control unit may control the pair of address selecting units in such a manner that if the data is to be interleaved, the output of the second address generating unit is selected as the writing address while the output of the first address generating unit is selected as the reading address, respectively, and if the data is to be deinterleaved, the output of the first address generating unit is selected as the writing address while the output of the second address generating unit is selected as the reading address, respectively.
In both of the above cases, one of the interleaving function and the deinterleaving function can be selected by simply selecting one of the outputs from the address generating units. Therefore, the present apparatus can be constructed to have a very simple arrangement.
Also in the present interleave-deinterleave apparatus, the second address generating unit may include a random pattern holding unit for holding random pattern information which is used for rearranging the sequence of addresses, generated from the first address generating unit, at random and which is used for outputting the rearranged addresses. Also in this case, it becomes unnecessary to prepare two sets of random pattern information for interleave operation and deinterleave operation, (i.e., the first address generating unit can be made to serve as not only a unit for interleave operation but also a unit for deinterleave operation). Therefore, cost for carrying out arithmetic operation requested upon determining the random pattern in advance can be remarkably reduced, and moreover the present apparatus can be made smaller and constructed at an extremely low cost.